package data_structures_and_algorithms.list_node;

import common.ListNode;

/**
 * @ClassName Code_0025_reverseListNodeInKGroup
 * @Description: K个节点一组反转链表
 *
 * https://leetcode.cn/problems/reverse-nodes-in-k-group/submissions/
 * @Author: yongliang.ma
 * @Create_time:2022/10/28 11:22
 */
public class Code_0025_reverseListNodeInKGroup {

    // 就是这样的做题节奏，分析清除思路，设计好一个方法的实现需要哪些小的子方法，然后将子方法逐个搞定
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode target = new ListNode(0);
        target.next = head;
        ListNode prePart = target;
        // 节点分为四层：前一部分，待反转的链表的左节点 和 右节点，和后续节点
        ListNode L = null, R = null, nextPart = null;
        while (true){
            L = prePart.next;
            R = getKthNode(prePart, k);
            if (R == null)
                break;
            nextPart = R.next;

            // 反转L R之间的链表
            reverseLToR(L, R);

            // 设置头尾相接位置
            prePart.next = R;
            L.next = nextPart;

            // 移动指针位置，继续
            prePart = L;// 注意这里是从L算作prePart，已经反转链表了

        }
        return target.next;
    }

    public ListNode getKthNode(ListNode prePart, int k){
        ListNode cur = prePart;
        while (k > 0 && cur != null){
            cur = cur.next;
            k--;
        }
        return cur;
    }

    public void reverseLToR(ListNode L, ListNode R){
        ListNode pre = null, cur = L;
        while (pre != R){
            ListNode next = cur.next;
            cur.next = pre;

            pre = cur;

            cur = next;
        }

    }
}
